package leetcode.editor.cn;
//累加数 是一个字符串，组成它的数字可以形成累加序列。 
//
// 一个有效的 累加序列 必须 至少 包含 3 个数。除了最开始的两个数以外，序列中的每个后续数字必须是它之前两个数字之和。 
//
// 给你一个只包含数字 '0'-'9' 的字符串，编写一个算法来判断给定输入是否是 累加数 。如果是，返回 true ；否则，返回 false 。 
//
// 说明：累加序列里的数，除数字 0 之外，不会 以 0 开头，所以不会出现 1, 2, 03 或者 1, 02, 3 的情况。 
//
// 
//
// 示例 1： 
//
// 
//输入："112358"
//输出：true 
//解释：累加序列为: 1, 1, 2, 3, 5, 8 。1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8
// 
//
// 示例 2： 
//
// 
//输入："199100199"
//输出：true 
//解释：累加序列为: 1, 99, 100, 199。1 + 99 = 100, 99 + 100 = 199 
//
// 
//
// 提示： 
//
// 
// 1 <= num.length <= 35 
// num 仅由数字（0 - 9）组成 
// 
//
// 
//
// 进阶：你计划如何处理由过大的整数输入导致的溢出? 
//
// 👍 414 👎 0

/**
 * 提示要处理由过大的整数输入导致的溢出，转成 log 类型可以解决，但是这个肯定不是最好的解决办法
 * <p>
 * 执行耗时:0 ms,击败了100.00% 的Java用户
 * 内存消耗:39.6 MB,击败了47.69% 的Java用户
 */
public class Q306_AdditiveNumber {
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public boolean isAdditiveNumber(String num) {
            int m = num.length();
            if (m < 3) return false;

            for (int i = 1; i < m; i++) {
                // 判断长度，减少转成数字的测试
                if (i > m - i) {
                    break;
                }
                for (int j = i + 1; j < m; j++) {
                    // 判断长度，减少转成数字的测试
                    if (j - i > m - j) {
                        break;
                    }
                    if (check(i, j, num)) {
                        return true;
                    }
                }
            }

            return false;
        }

        private boolean check(int i, int j, String num) {
            String mStr = num.substring(0, i);
            if (mStr.length() > 1 && mStr.startsWith("0")) {
                return false;
            }
            long m = Long.parseLong(mStr);

            String nStr = num.substring(i, j);
            if (nStr.length() > 1 && nStr.startsWith("0")) {
                return false;
            }
            long n = Long.parseLong(nStr);
            while (true) {
                long sum = m + n;
                String str = String.valueOf(sum);
                int k = j + str.length();

                // 判断长度，减少转成数字的测试
                if (k > num.length()) return false;

                if (str.equals(num.substring(j, k))) {
                    if (k == num.length()) {
                        return true;
                    }

                    m = n;
                    n = sum;
                    j = k;
                } else {
                    return false;
                }
            }
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q306_AdditiveNumber().new Solution();
        // TO TEST
        System.out.println(solution.isAdditiveNumber("0235813"));
        System.out.println(solution.isAdditiveNumber("199100199"));
        System.out.println(solution.isAdditiveNumber("112358"));
    }
}